Khot, Subhash A. : rechercher sur Z-Library

Le plus grand référentiel d'articles scientifiques au monde. 70,000,000+ d'articles gratuitement.

Don't use scam websites

Livres
Articles (66)
Les plus populaires
Liste
- Liste
- Tableau

1

Improved lower bounds on the randomized complexity of graph properties

Amit Chakrabarti, Subhash Khot

Journal:

Random Structures & Algorithms

Année:

2007

Langue:

english

Fichier:

PDF, 163 KB

english, 2007

2

Nonembeddability theorems via Fourier analysis

Subhash Khot, Assaf Naor

Journal:

Mathematische Annalen

Année:

2006

Langue:

english

Fichier:

PDF, 288 KB

english, 2006

3

Hardness of approximating the Shortest Vector Problem in high norms

Journal:

Journal of Computer and System Sciences

Année:

2006

Langue:

english

Fichier:

PDF, 232 KB

english, 2006

4

Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

Journal:

SIAM Journal on Computing

Année:

2006

Langue:

english

Fichier:

PDF, 475 KB

english, 2006

5

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Dinur, Irit, Guruswami, Venkatesan, Khot, Subhash, Regev, Oded

Journal:

SIAM Journal on Computing

Année:

2005

Langue:

english

Fichier:

PDF, 242 KB

english, 2005

6

Hardness of approximating the shortest vector problem in lattices

Journal:

Journal of the ACM

Année:

2005

Langue:

english

Fichier:

PDF, 182 KB

english, 2005

7

Combinatorial theorems about embedding trees on the real line

Amit Chakrabarti, Subhash Khot

Journal:

Journal of Graph Theory

Année:

2011

Langue:

english

Fichier:

PDF, 161 KB

english, 2011

8

Cell-probe lower bounds for the partial match problem

T.S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani

Journal:

Journal of Computer and System Sciences

Année:

2004

Langue:

english

Fichier:

PDF, 263 KB

english, 2004

9

Fitting algebraic curves to noisy data

Sanjeev Arora, Subhash Khot

Journal:

Journal of Computer and System Sciences

Année:

2003

Langue:

english

Fichier:

PDF, 219 KB

english, 2003

10

Parameterized complexity of finding subgraphs with hereditary properties

Subhash Khot, Venkatesh Raman

Journal:

Theoretical Computer Science

Année:

2002

Langue:

english

Fichier:

PDF, 143 KB

english, 2002

11

Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions

Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta

Journal:

Année:

2008

Langue:

english

Fichier:

PDF, 347 KB

english, 2008

12

Vertex cover might be hard to approximate to within

Subhash Khot, Oded Regev

Journal:

Journal of Computer and System Sciences

Année:

2008

Langue:

english

Fichier:

PDF, 221 KB

english, 2008

13

On the hardness of learning intersections of two halfspaces

Subhash Khot, Rishi Saket

Journal:

Journal of Computer and System Sciences

Année:

2011

Langue:

english

Fichier:

PDF, 232 KB

english, 2011

14

Grothendieck-Type Inequalities in Combinatorial Optimization

Subhash Khot, Assaf Naor

Journal:

Communications on Pure and Applied Mathematics

Année:

2012

Langue:

english

Fichier:

PDF, 344 KB

english, 2012

15

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Subhash Khot, Assaf Naor

Journal:

Random Structures & Algorithms

Année:

2012

Langue:

english

Fichier:

PDF, 321 KB

english, 2012

16

Hardness of Approximating the Closest Vector Problem with Pre-Processing

Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, Nisheeth K. Vishnoi

Journal:

Computational Complexity

Année:

2011

Langue:

english

Fichier:

PDF, 234 KB

english, 2011

17

Evasiveness of Subgraph Containment and Related Properties

Chakrabarti, Amit, Khot, Subhash, Shi, Yaoyun

Journal:

SIAM Journal on Computing

Année:

2001

Langue:

english

Fichier:

PDF, 159 KB

english, 2001

18

Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

Khot, Subhash, Kindler, Guy, Mossel, Elchanan, O’Donnell, Ryan

Journal:

SIAM Journal on Computing

Année:

2007

Langue:

english

Fichier:

PDF, 382 KB

english, 2007

19

On Agnostic Learning of Parities, Monomials, and Halfspaces

Feldman, Vitaly, Gopalan, Parikshit, Khot, Subhash, Ponnuswami, Ashok Kumar

Journal:

SIAM Journal on Computing

Année:

2009

Langue:

english

Fichier:

PDF, 486 KB

english, 2009

20

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

Gopalan, Parikshit, Khot, Subhash, Saket, Rishi

Journal:

SIAM Journal on Computing

Année:

2010

Langue:

english

Fichier:

PDF, 337 KB

english, 2010

21

On Earthmover Distance, Metric Labeling, and 0-Extension

Karloff, Howard, Khot, Subhash, Mehta, Aranyak, Rabani, Yuval

Journal:

SIAM Journal on Computing

Année:

2009

Langue:

english

Fichier:

PDF, 266 KB

english, 2009

22

Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies

Khot, Subhash, Naor, Assaf

Journal:

SIAM Journal on Computing

Année:

2008

Langue:

english

Fichier:

PDF, 230 KB

english, 2008

23

$\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals

Khot, Subhash, Moshkovitz, Dana

Journal:

SIAM Journal on Computing

Année:

2013

Langue:

english

Fichier:

PDF, 471 KB

english, 2013

24

[IEEE 2010 IEEE 25th Annual Conference on Computational Complexity (CCC) - Cambridge, MA, USA (2010.06.9-2010.06.12)] 2010 IEEE 25th Annual Conference on Computational Complexity - On the Unique Games Conjecture (Invited Survey)

Année:

2010

Langue:

english

Fichier:

PDF, 439 KB

english, 2010

25

[ACM Press the thiry-fourth annual ACM symposium - Montreal, Quebec, Canada (2002.05.19-2002.05.21)] Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC '02 - On the power of unique 2-prover 1-round games

Année:

2002

Langue:

english

Fichier:

PDF, 193 KB

english, 2002

26

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

Austrin, Per, Khot, Subhash

Journal:

IEEE Transactions on Information Theory

Année:

2014

Langue:

english

Fichier:

PDF, 831 KB

english, 2014

27

[IEEE 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS) - New Brunswick, NJ, USA (2012.10.20-2012.10.23)] 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science - Hardness of Finding Independent Sets in Almost q-Colorable Graphs

Khot, Subhash, Saket, Rishi

Année:

2012

Langue:

english

Fichier:

PDF, 296 KB

english, 2012

28

[IEEE 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) - Providence, RI, USA (2007.10.21-2007.10.23)] 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) - Hardness of Reconstructing Multivariate Polynomials over Finite Fields

Gopalan, Parikshit, Khot, Subhash, Saket, Rishi

Année:

2007

Langue:

english

Fichier:

PDF, 380 KB

english, 2007

29

[IEEE 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) - Providence, RI, USA (2007.10.21-2007.10.23)] 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) - Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies

Khot, Subhash, Naor, Assaf

Année:

2007

Langue:

english

Fichier:

PDF, 340 KB

english, 2007

30

[IEEE 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) - Berkeley, CA, USA (2006.10.21-2006.10.24)] 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) - SDP gaps and UGC-hardness for MAXCUTGAIN

Khot, Subhash, O'Donnell, Ryan

Année:

2006

Langue:

english

Fichier:

PDF, 187 KB

english, 2006

31

[IEEE 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS) - Atlanta, GA, USA (2009.10.25-2009.10.27)] 2009 50th Annual IEEE Symposium on Foundations of Computer Science - SDP Integrality Gaps with Local ell_1-Embeddability

Khot, Subhash, Saket, Rishi

Année:

2009

Langue:

english

Fichier:

PDF, 313 KB

english, 2009

32

[IEEE 2009 24th Annual IEEE Conference on Computational Complexity (CCC) - Paris, France (2009.07.15-2009.07.18)] 2009 24th Annual IEEE Conference on Computational Complexity - Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs

Austrin, Per, Khot, Subhash, Safra, Muli

Année:

2009

Langue:

english

Fichier:

PDF, 313 KB

english, 2009

33

[IEEE 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS) - Las Vegas, NV, USA (2010.10.23-2010.10.26)] 2010 IEEE 51st Annual Symposium on Foundations of Computer Science - Hardness of Finding Independent Sets in Almost 3-Colorable Graphs

Dinur, Irit, Khot, Subhash, Perkins, Will, Safra, Muli

Année:

2010

Langue:

english

Fichier:

PDF, 448 KB

english, 2010

34

[IEEE 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) - Berkeley, CA, USA (2006.10.21-2006.10.24)] 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) - New Results for Learning Noisy Parities and Halfspaces

Feldman, Vitaly, Gopalan, Parikshit, Khot, Subhash, Ponnuswami, Ashok

Année:

2006

Langue:

english

Fichier:

PDF, 170 KB

english, 2006

35

[IEEE 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) - Philadelphia, PA, USA (2008.10.25-2008.10.28)] 2008 49th Annual IEEE Symposium on Foundations of Computer Science - Hardness of Minimizing and Learning DNF Expressions

Khot, Subhash, Saket, Rishi

Année:

2008

Langue:

english

Fichier:

PDF, 364 KB

english, 2008

36

[IEEE 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS) - Atlanta, GA, USA (2009.10.25-2009.10.27)] 2009 50th Annual IEEE Symposium on Foundations of Computer Science - Optimal Long Code Test with One Free Bit

Bansal, Nikhil, Khot, Subhash

Année:

2009

Langue:

english

Fichier:

PDF, 290 KB

english, 2009

37

[IEEE 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) - Philadelphia, PA, USA (2008.10.25-2008.10.28)] 2008 49th Annual IEEE Symposium on Foundations of Computer Science - Approximate Kernel Clustering

Khot, Subhash, Naor, Assaf

Année:

2008

Langue:

english

Fichier:

PDF, 327 KB

english, 2008

38

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Khot, Subhash A., Popat, Preyas, Vishnoi, Nisheeth K.

Journal:

SIAM Journal on Computing

Année:

2014

Langue:

english

Fichier:

PDF, 290 KB

english, 2014

39

[IEEE 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS) - Palm Springs, CA, USA (2011.10.22-2011.10.25)] 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science - A Two Prover One Round Game with Strong Soundness

Khot, Subhash, Safra, Muli

Année:

2011

Langue:

english

Fichier:

PDF, 491 KB

english, 2011

40

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1

Khot, Subhash A., Vishnoi, Nisheeth K.

Journal:

Journal of the ACM

Année:

2015

Langue:

english

Fichier:

PDF, 482 KB

english, 2015

41

Approximate Kernel Clustering

Khot, Subhash, Naor, Assaf

Journal:

Année:

2009

Langue:

english

Fichier:

PDF, 288 KB

english, 2009

42

[ACM Press the thirty-eighth annual ACM symposium - Seattle, WA, USA (2006.05.21-2006.05.23)] Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06 - On earthmover distance, metric labeling, and 0-extension

Karloff, Howard, Khot, Subhash, Mehta, Aranyak, Rabani, Yuval

Année:

2006

Langue:

english

Fichier:

PDF, 250 KB

english, 2006

43

[ACM Press the thirty-eighth annual ACM symposium - Seattle, WA, USA (2006.05.21-2006.05.23)] Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06 - Integrality gaps for sparsest cut and minimum linear arrangement problems

Devanur, Nikhil R., Khot, Subhash A., Saket, Rishi, Vishnoi, Nisheeth K.

Année:

2006

Langue:

english

Fichier:

PDF, 265 KB

english, 2006

44

[ACM Press the thirty-fifth ACM symposium - San Diego, CA, USA (2003.06.09-2003.06.11)] Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03 - Cell-probe lower bounds for the partial match problem

Jayram, T. S., Khot, Subhash, Kumar, Ravi, Rabani, Yuval

Année:

2003

Langue:

english

Fichier:

PDF, 166 KB

english, 2003

45

[ACM Press the 43rd annual ACM symposium - San Jose, California, USA (2011.06.06-2011.06.08)] Proceedings of the 43rd annual ACM symposium on Theory of computing - STOC '11 - NP-hardness of approximately solving linear equations over reals

Khot, Subhash, Moshkovitz, Dana

Année:

2011

Langue:

english

Fichier:

PDF, 415 KB

english, 2011

46

[ACM Press the 4th conference - Berkeley, California, USA (2013.01.09-2013.01.12)] Proceedings of the 4th conference on Innovations in Theoretical Computer Science - ITCS '13 - A characterization of approximation resistance for even k-partite CSPs

Austrin, Per, Khot, Subhash

Année:

2013

Langue:

english

Fichier:

PDF, 647 KB

english, 2013

47

[ACM Press the thiry-fourth annual ACM symposium - Montreal, Quebec, Canada (2002.05.19-2002.05.21)] Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC '02 - Hardness results for approximate hypergraph coloring

Année:

2002

Langue:

english

Fichier:

PDF, 238 KB

english, 2002

48

[ACM Press the 40th annual ACM symposium - Victoria, British Columbia, Canada (2008.05.17-2008.05.20)] Proceedings of the fourtieth annual ACM symposium on Theory of computing - STOC 08 - On hardness of learning intersection of two halfspaces

Khot, Subhash, Saket, Rishi

Année:

2008

Langue:

english

Fichier:

PDF, 237 KB

english, 2008

49

[ACM Press the thirty-sixth annual ACM symposium - Chicago, IL, USA (2004.06.13-2004.06.16)] Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 - A new PCP outer verifier with applications to homogeneous linear equations and max-bisection

Holmerin, Jonas, Khot, Subhash

Année:

2004

Langue:

english

Fichier:

PDF, 243 KB

english, 2004

50

[ACM Press the 40th annual ACM symposium - Victoria, British Columbia, Canada (2008.05.17-2008.05.20)] Proceedings of the fourtieth annual ACM symposium on Theory of computing - STOC 08 - Unique games on expanding constraint graphs are easy

Arora, Sanjeev, Khot, Subhash A., Kolla, Alexandra, Steurer, David, Tulsiani, Madhur, Vishnoi, Nisheeth K.

Année:

2008

Langue:

english

Fichier:

PDF, 270 KB

english, 2008